Question 1
Why is it important for the scheduler to distinguish I/O-bound programs from CPU-bound programs?
I/O-bound programs perform only a small amount of computation before performing I/O operations.
These programs typically do not consume the entire CPU quantum.
On the other hand, CPU-bound programs use their entire quantum without performing blocking I/O operations.
By distinguishing between I/O-bound and CPU-bound programs, the scheduler can allocate higher priority to I/O-bound programs,
allowing them to execute ahead of CPU-bound programs, improving resource utilization and system responsiveness.
Question 2
What is the difference between preemptive and non-preemptive scheduling?
Preemptive scheduling allows a process to be interrupted in the middle of its execution, taking the CPU away and allocating it to another process.
Non-preemptive scheduling ensures that a process relinquishes control of the CPU only when it has completed its current CPU burst.
Question 3
Explain the difference in the degree to which the following scheduling algorithms discriminate in favor of short processes.
a) FCFS (First Come, First Served) – FCFS discriminates against short jobs since any short job arriving after long jobs will have to wait longer.
b) RR (Round Robin) – RR treats all jobs equally by giving them equal CPU time (quantum).
As a result, short jobs will finish quicker since they will complete within their first CPU burst.
Question 4
Consider the following set of processes with the length of the CPU-burst time given in milliseconds:
Process | Burst-time | Arrival time
P1 | 10 | 0
P2 | 2 | 1
P3 | 3 | 2
P4 | 1 | 3
P5 | 5 | 4
a) Draw the Gantt charts illustrating the execution of these processes using FCFS, Non-Preemptive SJF,
Preemptive SJF (Shortest Remaining Time First), and RR (quantum=2) scheduling.
Gantt Charts:
b) What is the turnaround time of each process and also average turnaround time for each of the scheduling algorithms?
Turnaround time = Finish Time - Arrival Time
| Process | FCFS | RR | Non-preemptive SJF | Preemptive SJF |
|---------|------|----|---------------------|----------------|
| P1 | 10 | 21 | 10 | 21 |
| P2 | 11 | 3 | 12 | 2 |
| P3 | 13 | 10 | 14 | 5 |
| P4 | 13 | 6 | 8 | 1 |
| P5 | 17 | 15 | 17 | 8 |
Average Turnaround Time:
- **FCFS:** 64/5 = 12.8ms
- **RR:** 55/5 = 11ms
- **Non-preemptive SJF:** 61/5 = 12.2ms
- **Preemptive SJF:** 37/5 = 7.4ms
c) What is the waiting time of each process and also average waiting time for each of the scheduling algorithms?
Waiting Time = Turnaround Time - CPU Burst Time
| Process | FCFS | RR | Non-preemptive SJF | Preemptive SJF |
|---------|------|-----|---------------------|----------------|
| P1 | 0 | 11 | 0 | 11 |
| P2 | 9 | 1 | 10 | 0 |
| P3 | 10 | 7 | 11 | 2 |
| P4 | 12 | 5 | 7 | 0 |
| P5 | 12 | 10 | 12 | 3 |
Average Waiting Time:
- **FCFS:** 43/5 = 8.6ms
- **RR:** 34/5 = 6.8ms
- **Non-preemptive SJF:** 40/5 = 8ms
- **Preemptive SJF:** 16/5 = 3.2ms
d) Which of the above scheduling algorithm results in the minimal average waiting time (over all processes)?
Preemptive SJF results in the minimal average waiting time.
Question 5
Consider the following processes with the length of a CPU burst time given in milliseconds. Assume that lower numbers represent higher priority.
Process | Arrival Time | Priority | Burst Time
P0 | 0 | 2 | 8
P5 | 0 | 1 | 6
P1 | 4 | 5 | 15
P4 | 9 | 4 | 13
P2 | 7 | 3 | 9
P3 | 13 | 1 | 5
a) Draw the Gantt Charts illustrating the execution of these processes using the following scheduling algorithms.
Gantt Charts:
b) Calculate the average turnaround time and waiting time for all the above scheduling algorithms.
Average Turnaround Time:
- **Non-preemptive SJF:** 131/6 = 21.83ms
- **Preemptive SJF:** 131/6 = 21.83ms
- **Non-preemptive Priority:** 131/6 = 21.83ms
- **Preemptive Priority:** 135/6 = 22.5ms
- **RR:** 199/6 = 33.17ms
Average Waiting Time:
- **Non-preemptive SJF:** 75/6 = 12.5ms
- **Preemptive SJF:** 75/6 = 12.5ms
- **Non-preemptive Priority:** 75/6 = 12.5ms
- **Preemptive Priority:** 79/6 = 13.17ms
- **RR:** 143/6 = 23.83ms